package com.duing.array;

import java.util.*;

public class SingleNumber {

    public static void main(String[] args) {
        int[] test = {4, 1, 2, 1, 2};
        System.out.println(singleNumber1(test));
    }

    //暴力循环法  O(n^2)
    public static int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (map.containsKey(num)) {
                int count = map.get(num);
                map.put(num, ++count);
                continue;
            }

            map.put(num, 1);
        }

        for (Integer num : map.keySet()) {
            if (map.get(num) == 1) {
                return num;
            }
        }
        return -1;
    }


    //遍历 nums 中的每一个元素
    //如果某个 nums 中的数字是新出现的，则将它添加到列表中
    //如果某个数字已经在列表中，删除它
    // O(n)
    public static int singleNumber1(int[] nums) {
        Set<Integer> set = new HashSet();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (set.contains(num)) {
                set.remove(num);
                continue;
            }
            set.add(num);
        }
        return set.iterator().next();
    }


    //优化版
    public static int singleNumber2(int[] nums) {
        Set<Integer> set = new HashSet();
        int remain = 0;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (set.contains(num)) {
                remain -= num;
                continue;
            }
            set.add(num);
            remain += num;
        }
        return remain;
    }

    public static int singleNumber3(int[] nums) {
        if (nums.length == 1) return nums[0];
        // 快排  时间复杂度 O(nlogn)
        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i < len - 1; ) {
            if (nums[i] == nums[i + 1]) {
                i += 2;
                continue;
            }
            return nums[i];
        }
        // 这个判断甚至可以没有
        if (nums[len - 1] != nums[len - 2]) {
            return nums[len - 1];
        }
        return -1;
    }


    //异或
    public static int singleNumber4(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            result ^= nums[i];
        }
        return result;
    }

}
